package done.easy_101_200;

import com.study.common.TreeNode;
import lombok.extern.slf4j.Slf4j;
import org.junit.Test;

import java.util.*;

/**
 * 107. Binary Tree Level Order Traversal II 二叉树的深度搜索
 * <p>
 * 给定一个二叉树，返回其节点值自底向上的层次遍历。
 * （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
 * <p>
 * 例如：
 * 给定二叉树 [3,9,20,null,null,15,7],
 * <p>
 * 3
 * /    \
 * 9      20
 * / \    /  \
 * 1   2  15   7
 * 返回其自底向上的层次遍历为：
 * [
 * [15,7],
 * [9,20],
 * [3]
 * ]
 * <p>
 * 解答：
 * 【3】 -> null        queue  第一次
 * /       \
 * 9   ->   20  -> null   queue  第二次
 * / \      /   \
 * 1 -> 2 -> 15 -> 7 -> null queue  第三次
 * <p>
 * <p>
 * 2019-03-24 12:41 PM
 **/
@Slf4j
public class BinaryTreeLevelOrderTraversalII {

    @SuppressWarnings("all")
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        // 190324 first
        return null;
    }

    @Test
    public void test() {
        TreeNode root = new TreeNode(3,
                new TreeNode(9,
                        1, 2),
                new TreeNode(20,
                        15, 7));
        log.info("result:{}", levelOrderBottom(root));
    }
}












































/*
public List<List<Integer>> levelOrderBottom(TreeNode root) {
    ArrayList<List<Integer>> res = new ArrayList<>();
    if(root == null)    return res;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while(!queue.isEmpty()){
        int count = queue.size();
        ArrayList<Integer> list = new ArrayList<>();
        while(count > 0){
            TreeNode node = queue.poll();
            list.add(node.val);
            if(node.left != null)
                queue.add(node.left);
            if(node.right != null)
                queue.add(node.right);
            count--;
        }
        res.add(0, list);
    }
    return res;
}
*/
